//给你一个整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
// Related Topics 数组 动态规划 回溯 👍 946 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：目标和
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P494_TargetSum {
    public static void main(String[] args) {
        Solution solution = new P494_TargetSum().new Solution();
        int[] nums = MyUtil.createArray(1, 1, 1, 1, 1);
        MyUtil.print(solution.findTargetSumWays(nums, 5));
        MyUtil.print(solution.findTargetSumWaysDp(nums, 5));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // [1], -100
        public int findTargetSumWays(int[] nums, int target) {
            return findTargetSumWaysRecursion(nums, target);
//            return findTargetSumWaysDp(nums, target);
        }

        public int findTargetSumWaysRecursion(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int N = nums.length;
            // 总和
            int sum = 0;
            for (int x : nums) {
                sum += Math.abs(x);
            }
            // target比所有数加起来还大或者比所有数还小
            if (target > sum || target < -1 * sum) {
                return 0;
            }
            return process(nums, 0, target);
        }

        /**
         * index及其往后数字组合成的目标和为rest的方法有多少种
         */
        private int process(int[] nums, int index, int rest) {
            // 到最后了
            if (index == nums.length) {
                return rest == 0 ? 1 : 0;
            }
            // 当前数字+
            int p1 = process(nums, index + 1, rest - nums[index]);
            // 当前数字-
            int p2 = process(nums, index + 1, rest + nums[index]);
            return p1 + p2;
        }

        public int findTargetSumWaysDp(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int N = nums.length;
            // 总和
            int sum = 0;
            for (int x : nums) {
                sum += Math.abs(x);
            }
            // target比所有数加起来还大或者比所有数还小
            if (target > sum || target < -1 * sum) {
                return 0;
            }
            // 防止rest为负数，rest最大到两倍的sum
            int[][] dp = new int[N + 1][2 * sum + 1];
            dp[N][0 + sum] = 1;
            // 整体从下往上，内部从左到右
            for (int index = N - 1; index >= 0; index--) {
                for (int rest = 0; rest <= 2 * sum; rest++) {
                    int left = rest - nums[index];
                    if (left >= 0) {
                        dp[index][rest] += dp[index + 1][left];
                    }
                    int right = rest + nums[index];
                    if (right <= 2 * sum) {
                        dp[index][rest] += dp[index + 1][right];
                    }
                }
            }
            return dp[0][target + sum];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}